home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 4 / Amiga Tools 4.iso / tools / packer / xpkilzr / source / ilzr.c < prev    next >
C/C++ Source or Header  |  1996-02-26  |  11KB  |  287 lines
  1.  
  2.  
  3. /**-----------------------------------------------------------------------
  4.   *   Bloque de includes, por fin me ocupan menos de una pagina de
  5.   * impresisn, lo que hay que hacer para tener todos los prototipos..
  6.   *
  7.   **/
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <string.h>
  12. #include <ctype.h>
  13.  
  14. #define NO_SUB_PRAGMAS
  15. #include <libraries/xpksub.h>
  16.  
  17. #include "bitio.h"      /* custom includes */
  18.  
  19. /**-----------------------------------------------------------------------
  20.   *   Bloque de constantes 'NEMOTECNICAS' para una mejor simplicidad
  21.   * de csdigo, lo siento si alguien cree que tengo demasiada tendencia
  22.   * a las palabras de origen sajsn, pero no puedo sufrir versiones 
  23.   * castellanas ni catalanas. Sera la costumbre.
  24.   *
  25.   **/
  26.  
  27. #define TRUE                  1
  28. #define FALSE                 0
  29. #define NIL                   0
  30. #define UNUSED                0
  31. #define CONTROL               0L    /* Indicador de que control   */
  32. #define END_OF_FILE           0L    /* Indic. fin de fichero      */
  33. #define BITS_CHARS            8     /* 8 order-0 ; 16 order-1 ... */
  34.  
  35. #define WIND_BITS            14
  36. #define WIND_SIZE             ( 1 << WIND_BITS )
  37. #define WIND_MASK             ( WIND_SIZE - 1 )
  38. #define MOD_WIN( a )          ( ( a ) & WIND_MASK )
  39.  
  40. #define INIT_BIT_BUMP              8
  41.  
  42. #define BITS_LOOKAHEAD        4
  43. #define RAW_LOOKAHEAD         ( 1 << BITS_LOOKAHEAD ) 
  44.  
  45. #define MIN_MATCH             3     /* No lo toques o no funciona */
  46. #define MAX_MATCH             (RAW_LOOKAHEAD + MIN_MATCH -1 )
  47.  
  48. #define HASH_BITS             15    /* Sugiero mmnimo de 12 pero llega a 10 */
  49. #define HASH_SIZE            (unsigned)(1<<HASH_BITS)
  50. #define HASH_MASK             ( HASH_SIZE - 1)
  51. #define HASH_SHIFT            (( HASH_BITS + MIN_MATCH -1 )/MIN_MATCH) /* 5 */
  52.  
  53. #define MAX_HASH_COL          128
  54.  
  55. #define REHASH( h , c )      h = (( (( h )<<HASH_SHIFT) ^ ( c )) & HASH_MASK )
  56.  
  57.  
  58. /**-----------------------------------------------------------------------
  59.   *   Aqum se encuentran las variables globales, espero que no quede nada 
  60.   * pues en caso contrario uno no puede hacer residente el codigo
  61.   *
  62.   **/
  63.  
  64.  
  65. /**-----------------------------------------------------------------------
  66.   *   Definicisn de tipos a causa de mi vagancia al escribir, tambien
  67.   * simplifica considerablemente el entendimiento de los parametros.
  68.   *
  69.   **/
  70.  
  71. typedef unsigned char  CHARS;   /* Por si en el futuro amplio a order-1    */
  72.                               /* El 1.8 Speedup , 14% compresion-down( text ) */
  73.  
  74. /**-----------------------------------------------------------------------
  75.   *   Prototipos para todas estas paridas necesarias para compilar.
  76.   *
  77.   **/
  78.  
  79.  
  80. /**-----------------------------------------------------------------------
  81.   *   En un principio utilizaba la funcisn de HASH del COMRESS de GNU en
  82.   * UNIX, pero por motivos de eficiencia he tenido que cambiarla. La forma
  83.   * actual se inspira en el algoritmo de Rabin & Karp ( En el libro :
  84.   *   "Algorithms" de Sedgewick de Addison-Wesley p.252  )
  85.   *
  86.   **/
  87.  
  88. #define BestMatch( scan , matchpos , bestlen )                      \
  89.   {                                                                 \
  90.   if( (xparinbuf + matchpos) <= scan )                                             \
  91.     {                                                               \
  92.     ioaux    = 0;                                                   \
  93.     bestlen  = MIN_MATCH - 1;                                       \
  94.     scanend  = scan[ bestlen    ];                                  \
  95.     strend   = scan + MAX_MATCH;                                    \
  96.     current  = matchpos;                                            \
  97.     lastmatch= matchpos;                                            \
  98.     while( current != NIL &&  lastmatch >= current )                \
  99.       {                                                             \
  100.       match = xparinbuf + current;                                \
  101.       if( match[ bestlen   ] != scanend  ||                         \
  102.           *match             != *scan    ||                         \
  103.           *++match           != scan[1]     )                       \
  104.         {                                                           \
  105.         lastmatch  = current;                                       \
  106.         current    = prev[ current ];                               \
  107.         ioaux++;                                                    \
  108.         if( ioaux > MAX_HASH_COL )                                  \
  109.           break;                                                    \
  110.         continue;                                                   \
  111.         }                                                           \
  112.       scan+=2;    /*  do not try to put in the if condition    */   \
  113.       match++;                                                      \
  114.       do                                                            \
  115.         {                                                           \
  116.         }while( *++scan == *++match &&  *++scan == *++match &&      \
  117.                 *++scan == *++match &&  *++scan == *++match &&      \
  118.                 *++scan == *++match &&  *++scan == *++match &&      \
  119.                 *++scan == *++match &&  *++scan == *++match &&      \
  120.                 scan < strend );    /* Estraqo pero mejor codigo */ \
  121.       conta  = MAX_MATCH - (UBYTE)(strend - scan);  /* len para ahorrar */\
  122.       scan = strend - MAX_MATCH;                                    \
  123.       if( conta > bestlen )                                         \
  124.         {                                                           \
  125.         bestlen  = conta;                                           \
  126.         matchpos = current;                                         \
  127.         if( conta >= MAX_MATCH )                                    \
  128.           break;                                                    \
  129.         scanend   = scan[ bestlen     ];                            \
  130.         }                                                           \
  131.       lastmatch  = current;                                         \
  132.       current    = prev[ current ];                                 \
  133.       }                                                             \
  134.     }                                                               \
  135.   }
  136.  
  137.  
  138. /**-----------------------------------------------------------------------
  139.   *   En pocas lineas se adentrara al nucleo de todo el sistema de
  140.   * compresisn de datos, aunque parezca mentira intentare que el 
  141.   * sistema mantenga el coste ideal mmnimo, coste LINEAL??.
  142.   *   Esto son las mejores intenciones, ya veremos en que se nos queda.
  143.   *
  144.   **/
  145.  
  146. long __saveds __asm XpksPackChunk( REG __a0 XPARAMS *xpar )
  147. {
  148.     /*  variables para input - output   */
  149. register   UBYTE  inpmask;
  150.            UBYTE  outmask;
  151. register   CHARS *inpb;
  152.            CHARS *endinp;
  153. register   CHARS *outb;
  154.            CHARS *endout;
  155.            ULONG  ioaux;          /* tambien se usa en BestMach           */
  156.  
  157.   /*  varialbles utilizadas en BestMach   */
  158.            CHARS  scanend;
  159.            CHARS *strend;
  160.            CHARS *match;
  161.            UWORD  current;
  162.            UWORD  lastmatch;
  163.  
  164.     /*  bloque general de compres       */
  165.            UBYTE  lookahead;      /* siempre RAW_LOOKAHEAD < 255          */
  166.            UBYTE  matchlen;       /* siempre RAW_LOOKAHEAD < 255          */
  167.            UBYTE  replace;        /* cuanto se ha de ampliar "lookahead"  */
  168.            UBYTE  conta;          /* tambien se usa en BestMach           */
  169.            
  170.            long   bitcount;       /* es un LONG para compatibilidad       */
  171.            CHARS *bumpcode;
  172.            
  173.            CHARS *xparinbuf;      /* todo el mundo la utiliza             */
  174.            UWORD  hash_key;       /* actual hash value                    */
  175.            UWORD  matchpos;       /* position of matchlen                 */
  176. register   CHARS *actp;           /* posicion  en wwindow fich            */
  177. register   UWORD *head;           /* dictionary                           */
  178. register   UWORD *prev;           /* previous in the hash line            */
  179.  
  180. /**
  181.   * Bloque de inicializacsn + reserva de memoria para las tablas
  182.   *
  183.   **/
  184.  
  185.   if( !xpar->Sub[0] )
  186.     {
  187.     if( !(head = malloc( sizeof( UWORD ) * HASH_SIZE )) )
  188.       return( XPKERR_NOMEM );
  189.  
  190.     if( !(prev = malloc( sizeof( UWORD ) * (WIND_SIZE+MAX_MATCH) ) ) )
  191.       {
  192.       free( head );
  193.       return( XPKERR_NOMEM );
  194.       }
  195.     memset( head , NIL , HASH_SIZE*sizeof( UWORD ) ); /* head */
  196.     xpar->Sub[0]=(long)prev;
  197.     xpar->Sub[1]=(long)head;
  198.     }
  199.  
  200.                  /* previous y wwindow se autoinilizalizan */
  201.  
  202.   InitOutput();
  203.   InitInput();
  204.  
  205.   xparinbuf = xpar->InBuf;
  206.   bitcount  = INIT_BIT_BUMP;
  207.   bumpcode  = xparinbuf+(1<<INIT_BIT_BUMP);
  208.  
  209.   matchpos  = 0;     /* No hace falta pero evita un WARNING */
  210.   matchlen  = 0;
  211.   actp      = xparinbuf;
  212.   hash_key  = 0;
  213.  
  214. /**
  215.   * Bloque de la precarga necesaria para poder empezar el bucle
  216.   *
  217.   **/
  218.  
  219.   for( conta = 1 ; conta <= MAX_MATCH && EndOfFile() ; conta++ )
  220.     InputByte( );
  221.   
  222.   lookahead = conta-2;
  223.  
  224.  if( conta > 3 )
  225.     {
  226.     REHASH( hash_key , actp[1] );
  227.     REHASH( hash_key , actp[2] );
  228.     }
  229.  
  230. /**
  231.   *   Comienzo del bucle principal para la compresisn de datos
  232.   *
  233.   **/
  234.  
  235.   while( lookahead > 0 )
  236.     {
  237.     if( matchlen > lookahead )
  238.       matchlen = lookahead;
  239.     
  240.     if( matchlen < MIN_MATCH )   /* Sale a cuenta 2 bloque ? */
  241.       {
  242.       replace=1;
  243.       OutputBit( 1 );
  244.       OutputBits( (long )*actp , BITS_CHARS );
  245.       }
  246.     else
  247.       {
  248.       replace=matchlen;
  249.       if( actp > bumpcode )
  250.         {
  251.         bitcount++;
  252.         bumpcode  = xparinbuf + (1<<bitcount);
  253.         }
  254.       OutputBit( 0 );
  255.       OutputBits( (long)matchpos , bitcount );
  256.       OutputBits( (long)( matchlen - MIN_MATCH  ) , BITS_LOOKAHEAD );
  257.       }
  258.  
  259.     for( conta = 0 ; conta < replace ; conta++ )
  260.       {
  261.       if( EndOfFile() )
  262.         lookahead--;
  263.       else
  264.         InputByte( );
  265.  
  266.       actp++;
  267.  
  268.       REHASH( hash_key , actp[  MIN_MATCH -1 ] ); 
  269.  
  270.       prev[ actp - xparinbuf ] = matchpos = head [ hash_key ];
  271.       head[ hash_key ] = actp - xparinbuf;
  272.       }
  273.  
  274.     BestMatch( actp , matchpos , matchlen );    /* potente macro eh !! */
  275.   }
  276.  
  277. /**
  278.   *   No hace falta indicador de final de fichero pues se siempre
  279.   * la longitud,  tampoco libero los recursos, de esto se encarga
  280.   *                     XpkPackFree
  281.   *
  282.   **/
  283.   return( 0 );
  284. }
  285.  
  286. /************************** End of ILZR.C *************************/
  287.